#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义二叉链表
typedef struct node
{
    char data;           // 数据
    struct node *lchild; // 左子结点
    struct node *rchild; // 右子结点
    struct node *parent; // 父节点, 可以不需要
} BinNode, *BinTree;

// 链栈
typedef struct stack
{
    BinNode *data;
    struct stack *next;
} Stack, *LinkStack;

// 定义队列结点
typedef struct qnode
{
    BinNode *data;
    struct qnode *next;
} QNode;

// 链队列
typedef struct lNode
{
    QNode *front;
    QNode *rear;
} LNode, *LinkQueue;

//------------------------------------栈--------------------------
// 判空栈
int stackEmpty(LinkStack L)
{
    return L == NULL;
}

// 进栈, 这里修改的链栈本身,所以形参使用二级指针,实参传入链栈本身的地址
void push(LinkStack *L, BinNode *data)
{
    Stack *p = (LinkStack)malloc(sizeof(Stack));
    p->data = data;
    p->next = (*L);
    // 新元素放至栈顶
    (*L) = p;
    // printf("v=%c, p=%p, L=%p\n", data, p, (*L));
}

// 退栈(出栈)
BinNode *pop(LinkStack *L)
{
    if (stackEmpty((*L)))
    {
        printf(">>stack is empty!\n");
        exit(0);
    }

    Stack *p = (*L);
    // 传地址才会修改原始值
    BinNode *data = p->data;
    (*L) = p->next;
    free(p);
    return data;
}

// 获取栈顶元素
BinNode *getTop(LinkStack L)
{
    if (stackEmpty(L))
    {
        printf(">>stack is empty!\n");
        exit(0);
    }
    return L->data;
}

//----------------------------------队列----------------------
// 初始化链队列. 带头结点的链队列
void initQueue(LinkQueue LQ)
{
    LQ->front = (QNode *)malloc(sizeof(QNode));
    LQ->rear = LQ->front; // 尾指针等于头指针，修改尾指针相当于修改头指针
    // 带头结点
    LQ->rear->next = NULL;
}

// 判空队列
int queueEmpty(LinkQueue LQ)
{
    return LQ->front == LQ->rear;
}

// 入队
void enQueue(LinkQueue LQ, BinNode *data)
{
    QNode *p = (QNode *)malloc(sizeof(QNode));
    p->data = data;
    p->next = NULL;
    LQ->rear->next = p;
    // 队尾指针指向新的队尾结点
    LQ->rear = p;
}
// 出队
BinNode *deQueue(LinkQueue LQ)
{
    if (queueEmpty(LQ))
    {
        //   printf("queue is empty\n");
        exit(0);
    }

    QNode *p = LQ->front;
    // 头指针指向原对头结点
    LQ->front = LQ->front->next;
    free(p);
    return LQ->front->data;
}

// 获取队头元素
BinNode *getFront(LinkQueue LQ)
{
    if (queueEmpty(LQ))
    {
        // printf("getFront queue is empty\n");
        exit(0);
    }
    return LQ->front->next->data;
}

//----------------------------------其他方法----------------------
// 通过控制台输出获取字符数组
char *getCharList()
{
    int max = 99;
    char *chs = malloc(max);
    printf(">>>input char element: ");
    char ch;
    for (int i = 0; i < max; i++)
    {
        ch = getchar();
        if (ch == '\n')
        {
            // printf(">>endinput, charlen=%lu\n", strlen(chs));
            break;
        }
        chs[i] = ch;
    }

    return chs;
}

void printchar(char *str, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("====%c\n", str[i]);
    }
}
